package main

import (
	"container/list"
	"fmt"
)

//树的中序遍历

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归
func midOrder1(root *TreeNode) (res []int) {
	var mid func(*TreeNode)
	mid = func(node *TreeNode) {
		if node == nil {
			return
		}
		mid(node.Left)              //左
		res = append(res, node.Val) //中 （中序 就是中间 第二步实现）
		mid(node.Right)             //右
	}
	mid(root)
	return
}

// midOrder2 左->中->右
//非递归（迭代）借助栈
func midOrder2(root *TreeNode) (res []int) {
	if root == nil {
		return
	}
	var stack = list.New()
	//先将所有左节点找到 加入栈中（即把树的最左边那一条元素全部加入栈）
	for root != nil {
		stack.PushBack(root)
		root = root.Left
	}
	//其次对栈中每个节点先弹出加入到结果res中 再找到该节点的右节点的所有左节点加入栈中
	for stack.Len() > 0 {
		e := stack.Back()
		stack.Remove(e)             //出栈
		node := e.Value.(*TreeNode) //类型断言
		res = append(res, node.Val)
		//找到该节点的右节点 再搜索它的左节点加入栈中
		node = node.Right
		for node != nil {
			stack.PushBack(node)
			node = node.Left
		}
	}
	return res
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 3}
	A.Left.Left = &TreeNode{Val: 4}
	A.Left.Right = &TreeNode{Val: 5}
	A.Right.Left = &TreeNode{Val: 6}
	fmt.Println(midOrder1(A))
	fmt.Println(midOrder2(A))
}
